package week3.blog_code.exer1001;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 将n个盘子从'A'移动到'B'借助'C'
        dfs('A', 'B', 'C', n);
    }

    /**
     * 将n号盘子从src移动到dest
     * @param src 原位置
     * @param dest 目标位置
     * @param n 盘子编号
     */
    private static void move(char src, char dest, int n) {
        // 打印移动轨迹
        System.out.println(n + " " + src + " " + dest);
    }

    /**
     * 将盘子1-n从src借助辅助柱子tmp移动到dest柱子
     * @param src 原柱子
     * @param dest 目标柱子
     * @param tmp 辅助柱子
     * @param n 盘子个数
     */
    private static void dfs(char src, char dest, char tmp, int n) {
        if (n == 1) {
            // 只有一个盘子
            move(src, dest, 1);
        } else {
            // 有多个盘子
            // 1. 先移动前n - 1个盘子从src到tmp借助dest
            dfs(src, tmp, dest, n - 1);
            // 2. 然后将n号盘子从src移动到dest
            move(src, dest, n);
            // 3. 然后将前n - 1个盘子从tmp移动到dest借助src
            dfs(tmp, dest, src, n - 1);
        }
    }
}
